By train
If you have a sufficient sense of adventure and at least a small grip on the German language you can take regional trains that connect almost every small city with major hubs like Berlin, Dresden and Leipzig.There are train tickets intended only for use on regional trains, that are called Ländertickets state tickets and come as "Sachsen Ticket" or "Brandenburg Ticket" and are only valid on regional trains in Saxony and Saxony-Anhalt Sachsen and Sachsen-Anhalt or Brandendenburg, respectively.To get around by train gives you the possibility of getting in touch with the locals. Younger people and students are the most likely to speak English, so approach them for a chat and they might tell you about hidden gems worth visiting that no guidebook would ever cover.
By car
You can rent cars in all major airports and will find renting outlets in most bigger cities. Traveling by car is the most flexible and the network of motorways and major roads is sufficient to bring you anywhere in Eastern Germany within hours. It tends to be fairly expensive as well.
Note however that most car rentals deny having their cars taken to eastern European countries, including Poland and the Czech Republic. If you plan to visit these countries as well, you might chose to rent your car there, as those limitations do not apply the other way round.